package src.leetcode.backtrack.hard_0037;

import java.util.Arrays;

public class solveSudoku {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solveSudoku(new char[][]{
                        {'5','3','.','.','7','.','.','.','.'},
                        {'6','.','.','1','9','5','.','.','.'},
                        {'.','9','8','.','.','.','.','6','.'},
                        {'8','.','.','.','6','.','.','.','3'},
                        {'4','.','.','8','.','3','.','.','1'},
                        {'7','.','.','.','2','.','.','.','6'},
                        {'.','6','.','.','.','.','2','8','.'},
                        {'.','.','.','4','1','9','.','.','5'},
                        {'.','.','.','.','8','.','.','7','9'}});
        System.out.println("solution.board = " + Arrays.deepToString(solution.board));
        return;
    }
}



class Solution {
    char[][] board;
    public void solveSudoku(char[][] board) {
        this.board = board;
        dfs(1,1);
    }

    private boolean dfs(int col, int row) {
        if(board[col - 1][row - 1] != '.') {
            if(col == 9 && row == 9) return true;
            if(row == 9){
                if(dfs(col + 1, 1)) return true;
            }else {
                if(dfs(col,row + 1)) return true;
            }
            return false;
        }
        for(int i = 1; i <= 9; i++){
            if(check(col - 1, row - 1, i)) continue;
            board[col - 1][row - 1] = (char) (i + '0');
            if(col == 9 && row == 9) return true;
            if(row == 9){
                if(dfs(col + 1, 1)) return true;
            }else {
                if(dfs(col,row + 1)) return true;
            }
            board[col - 1][row - 1] = '.';
        }

        return false;
    }

    private boolean check(int row, int col, int num){
        if(board[row][col] != '.') return true;
        for (int i = 0; i < 9; i++) { // 判断行里是否重复
            if (board[row][i] == num + '0') {
                return true;
            }
        }
        for (int j = 0; j < 9; j++) { // 判断列里是否重复
            if (board[j][col] == num + '0') {
                return true;
            }
        }
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == num + '0') {
                    return true;
                }
            }
        }

        return false;
    }
}